<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>其他OJ模板 | whoway</title>
    <meta name="description" content="Personal Blog Website">
    <link rel="icon" href="/images/photo.jpg">
  <link rel="manifest" href="/images/photo.jpg">
  <link rel="apple-touch-icon" href="/images/photo.jpg">
  <meta http-quiv="pragma" cotent="no-cache">
  <meta http-quiv="pragma" cotent="no-cache,must-revalidate">
  <meta http-quiv="expires" cotent="0">
    
    <link rel="preload" href="/assets/css/0.styles.0dbae9ec.css" as="style"><link rel="preload" href="/assets/js/app.c70e21ad.js" as="script"><link rel="preload" href="/assets/js/67.26f84d32.js" as="script"><link rel="prefetch" href="/assets/js/10.15222a53.js"><link rel="prefetch" href="/assets/js/100.7e0e5a86.js"><link rel="prefetch" href="/assets/js/101.efd59f25.js"><link rel="prefetch" href="/assets/js/102.dfbdc06c.js"><link rel="prefetch" href="/assets/js/103.d3ab2109.js"><link rel="prefetch" href="/assets/js/104.117957ef.js"><link rel="prefetch" href="/assets/js/105.046e8ff3.js"><link rel="prefetch" href="/assets/js/106.aebdc17d.js"><link rel="prefetch" href="/assets/js/107.248733c2.js"><link rel="prefetch" href="/assets/js/108.a2fecadc.js"><link rel="prefetch" href="/assets/js/109.35196857.js"><link rel="prefetch" href="/assets/js/11.770642f2.js"><link rel="prefetch" href="/assets/js/110.cf3d973c.js"><link rel="prefetch" href="/assets/js/111.f985889a.js"><link rel="prefetch" href="/assets/js/112.ad614f41.js"><link rel="prefetch" href="/assets/js/113.f666653c.js"><link rel="prefetch" href="/assets/js/114.c6c3f384.js"><link rel="prefetch" href="/assets/js/115.e51d3c2f.js"><link rel="prefetch" href="/assets/js/116.4f4b39f5.js"><link rel="prefetch" href="/assets/js/117.99352e11.js"><link rel="prefetch" href="/assets/js/118.c6ae6572.js"><link rel="prefetch" href="/assets/js/119.4ccbe778.js"><link rel="prefetch" href="/assets/js/12.042a92ff.js"><link rel="prefetch" href="/assets/js/120.edda1c4f.js"><link rel="prefetch" href="/assets/js/121.30a638ed.js"><link rel="prefetch" href="/assets/js/122.6efcefb1.js"><link rel="prefetch" href="/assets/js/123.91e6665b.js"><link rel="prefetch" href="/assets/js/124.f27e3d7e.js"><link rel="prefetch" href="/assets/js/125.c75712d5.js"><link rel="prefetch" href="/assets/js/126.ed756cce.js"><link rel="prefetch" href="/assets/js/127.2f06c74c.js"><link rel="prefetch" href="/assets/js/128.d5f6f30e.js"><link rel="prefetch" href="/assets/js/129.508b7eed.js"><link rel="prefetch" href="/assets/js/13.b5280c37.js"><link rel="prefetch" href="/assets/js/130.dc05f9aa.js"><link rel="prefetch" href="/assets/js/131.e0ba69b1.js"><link rel="prefetch" href="/assets/js/132.d79bcaa4.js"><link rel="prefetch" href="/assets/js/133.34acc01a.js"><link rel="prefetch" href="/assets/js/134.dabf64d5.js"><link rel="prefetch" href="/assets/js/135.ad90c915.js"><link rel="prefetch" href="/assets/js/136.dbb0074f.js"><link rel="prefetch" href="/assets/js/137.284ad365.js"><link rel="prefetch" href="/assets/js/138.a4b6856f.js"><link rel="prefetch" href="/assets/js/139.c9c1e20f.js"><link rel="prefetch" href="/assets/js/14.df02ba38.js"><link rel="prefetch" href="/assets/js/140.8b0a9269.js"><link rel="prefetch" href="/assets/js/141.9c7759c5.js"><link rel="prefetch" href="/assets/js/142.a4201a82.js"><link rel="prefetch" href="/assets/js/143.d7da6e8c.js"><link rel="prefetch" href="/assets/js/144.5e48e65d.js"><link rel="prefetch" href="/assets/js/145.a0e2633c.js"><link rel="prefetch" href="/assets/js/146.3c775f9b.js"><link rel="prefetch" href="/assets/js/147.22add89a.js"><link rel="prefetch" href="/assets/js/148.cfde1009.js"><link rel="prefetch" href="/assets/js/149.ffc835b5.js"><link rel="prefetch" href="/assets/js/15.fbdfc4ee.js"><link rel="prefetch" href="/assets/js/150.406c4b20.js"><link rel="prefetch" href="/assets/js/151.b2040eea.js"><link rel="prefetch" href="/assets/js/152.7bc65661.js"><link rel="prefetch" href="/assets/js/153.1d7c65e3.js"><link rel="prefetch" href="/assets/js/154.1309de49.js"><link rel="prefetch" href="/assets/js/155.81d3ee1f.js"><link rel="prefetch" href="/assets/js/156.154a4ef2.js"><link rel="prefetch" href="/assets/js/16.e5eb6147.js"><link rel="prefetch" href="/assets/js/17.57853c4a.js"><link rel="prefetch" href="/assets/js/18.cb9d7518.js"><link rel="prefetch" href="/assets/js/19.f354dc47.js"><link rel="prefetch" href="/assets/js/2.570d8a23.js"><link rel="prefetch" href="/assets/js/20.b5af7fad.js"><link rel="prefetch" href="/assets/js/21.0b1928fe.js"><link rel="prefetch" href="/assets/js/22.f78666de.js"><link rel="prefetch" href="/assets/js/23.29c3f366.js"><link rel="prefetch" href="/assets/js/24.6f596516.js"><link rel="prefetch" href="/assets/js/25.14067b60.js"><link rel="prefetch" href="/assets/js/26.74ba4989.js"><link rel="prefetch" href="/assets/js/27.13d60edd.js"><link rel="prefetch" href="/assets/js/28.9523cb32.js"><link rel="prefetch" href="/assets/js/29.8ec842e9.js"><link rel="prefetch" href="/assets/js/3.3fb3d2e0.js"><link rel="prefetch" href="/assets/js/30.805597a8.js"><link rel="prefetch" href="/assets/js/31.831b195d.js"><link rel="prefetch" href="/assets/js/32.063c672d.js"><link rel="prefetch" href="/assets/js/33.6d93fac3.js"><link rel="prefetch" href="/assets/js/34.56e8263c.js"><link rel="prefetch" href="/assets/js/35.dbe688bb.js"><link rel="prefetch" href="/assets/js/36.dc5af2c1.js"><link rel="prefetch" href="/assets/js/37.0a7494f6.js"><link rel="prefetch" href="/assets/js/38.fe4fc171.js"><link rel="prefetch" href="/assets/js/39.f5ed5e92.js"><link rel="prefetch" href="/assets/js/4.2c405ec8.js"><link rel="prefetch" href="/assets/js/40.fe7e2714.js"><link rel="prefetch" href="/assets/js/41.30b0811d.js"><link rel="prefetch" href="/assets/js/42.76f52d62.js"><link rel="prefetch" href="/assets/js/43.e7bb0817.js"><link rel="prefetch" href="/assets/js/44.ead0e883.js"><link rel="prefetch" href="/assets/js/45.235df046.js"><link rel="prefetch" href="/assets/js/46.5f09e829.js"><link rel="prefetch" href="/assets/js/47.67116354.js"><link rel="prefetch" href="/assets/js/48.31f34543.js"><link rel="prefetch" href="/assets/js/49.10b5ebba.js"><link rel="prefetch" href="/assets/js/5.6f47322c.js"><link rel="prefetch" href="/assets/js/50.c0f0b7f1.js"><link rel="prefetch" href="/assets/js/51.5143f3bf.js"><link rel="prefetch" href="/assets/js/52.eeddfd48.js"><link rel="prefetch" href="/assets/js/53.eb790db5.js"><link rel="prefetch" href="/assets/js/54.8fe5421c.js"><link rel="prefetch" href="/assets/js/55.d8f9004b.js"><link rel="prefetch" href="/assets/js/56.62ac9b92.js"><link rel="prefetch" href="/assets/js/57.a9caec0d.js"><link rel="prefetch" href="/assets/js/58.f93fc522.js"><link rel="prefetch" href="/assets/js/59.a81a03aa.js"><link rel="prefetch" href="/assets/js/6.8c2ea393.js"><link rel="prefetch" href="/assets/js/60.ab782775.js"><link rel="prefetch" href="/assets/js/61.6dd12daf.js"><link rel="prefetch" href="/assets/js/62.76f4b01f.js"><link rel="prefetch" href="/assets/js/63.6f8a4742.js"><link rel="prefetch" href="/assets/js/64.6f8bb1fa.js"><link rel="prefetch" href="/assets/js/65.4120a44b.js"><link rel="prefetch" href="/assets/js/66.360c2d2b.js"><link rel="prefetch" href="/assets/js/68.68f45e5e.js"><link rel="prefetch" href="/assets/js/69.e311eb56.js"><link rel="prefetch" href="/assets/js/7.6762b2d7.js"><link rel="prefetch" href="/assets/js/70.cea82674.js"><link rel="prefetch" href="/assets/js/71.783ddcf7.js"><link rel="prefetch" href="/assets/js/72.e5467385.js"><link rel="prefetch" href="/assets/js/73.b8fb681b.js"><link rel="prefetch" href="/assets/js/74.1bae37db.js"><link rel="prefetch" href="/assets/js/75.024387e5.js"><link rel="prefetch" href="/assets/js/76.a8e53010.js"><link rel="prefetch" href="/assets/js/77.8c55500a.js"><link rel="prefetch" href="/assets/js/78.7ce90bf5.js"><link rel="prefetch" href="/assets/js/79.ef71713f.js"><link rel="prefetch" href="/assets/js/8.788a6364.js"><link rel="prefetch" href="/assets/js/80.acad589d.js"><link rel="prefetch" href="/assets/js/81.02670d10.js"><link rel="prefetch" href="/assets/js/82.53b7b1ac.js"><link rel="prefetch" href="/assets/js/83.99eb8581.js"><link rel="prefetch" href="/assets/js/84.d1535ce3.js"><link rel="prefetch" href="/assets/js/85.fe2b7de9.js"><link rel="prefetch" href="/assets/js/86.41850272.js"><link rel="prefetch" href="/assets/js/87.1cdc6df9.js"><link rel="prefetch" href="/assets/js/88.01bf3461.js"><link rel="prefetch" href="/assets/js/89.17c69819.js"><link rel="prefetch" href="/assets/js/9.3813842d.js"><link rel="prefetch" href="/assets/js/90.f6ae7e35.js"><link rel="prefetch" href="/assets/js/91.507bc284.js"><link rel="prefetch" href="/assets/js/92.90551782.js"><link rel="prefetch" href="/assets/js/93.dc442d78.js"><link rel="prefetch" href="/assets/js/94.315f4e94.js"><link rel="prefetch" href="/assets/js/95.ccd6c6bf.js"><link rel="prefetch" href="/assets/js/96.0c6d89d0.js"><link rel="prefetch" href="/assets/js/97.1a9f10a9.js"><link rel="prefetch" href="/assets/js/98.43be3caa.js"><link rel="prefetch" href="/assets/js/99.54c8207b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.0dbae9ec.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">whoway</span></a> <div class="links" style="max-width:nullpx;"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" class="nav-link">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link router-link-active">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav>  <ul class="sidebar-links"><li><div class="sidebar-group first"><p class="sidebar-heading open"><span>其他OJ模板</span> <!----></p> <ul class="sidebar-group-items"><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_01-大数算法『模板』" class="sidebar-link">01.大数算法『模板』</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_1-1-大数加法" class="sidebar-link">1.1.大数加法</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_1-2-大数乘法⭐️" class="sidebar-link">1.2.大数乘法⭐️</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_1-3-大数阶乘" class="sidebar-link">1.3.大数阶乘</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_02-stl提取出“全排列”『模板』" class="sidebar-link">02.STL提取出“全排列”『模板』</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_2-1-不含重复数字-可包含重复数字『均可』" class="sidebar-link">2.1.不含重复数字/可包含重复数字『均可』</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_03-马拉车算法『模板』" class="sidebar-link">03.马拉车算法『模板』</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_3-1-马拉车算法杂谈" class="sidebar-link">3.1.马拉车算法杂谈</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_3-2-代码实现" class="sidebar-link">3.2.代码实现</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_04-求众数『模板』" class="sidebar-link">04.求众数『模板』</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_4-1-『众数的广泛例子』" class="sidebar-link">4.1.『众数的广泛例子』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_4-2-面试题-17-10-主要元素『众数的特例』" class="sidebar-link">4.2.面试题 17.10. 主要元素『众数的特例』</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#摩尔投票法讲解：" class="sidebar-link">摩尔投票法讲解：</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_4-3-『众数的特例-特例』229-求众数-ii" class="sidebar-link">4.3.『众数的特例+特例』229. 求众数 II</a></li></ul></li><li><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_05-位运算" class="sidebar-link">05.位运算</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_5-1-交换" class="sidebar-link">5.1.交换</a></li><li class="sidebar-sub-header"><a href="/03.Software/01.DataStructureAndAlgorithm/TemplateLibrary/Part04.%E5%85%B6%E4%BB%96OJ%E6%A8%A1%E6%9D%BF.html#_5-2-异或的性质" class="sidebar-link">5.2.异或的性质</a></li></ul></li></ul></div></li></ul> </div> <div class="page"> <div class="content"><h1 id="其他oj模板"><a href="#其他oj模板" class="header-anchor">#</a> 其他OJ模板</h1> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>&lt;font style=&quot;background:yellow&quot;&gt;
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><h2 id="_01-大数算法『模板』"><a href="#_01-大数算法『模板』" class="header-anchor">#</a> 01.大数算法『模板』</h2> <h3 id="_1-1-大数加法"><a href="#_1-1-大数加法" class="header-anchor">#</a> 1.1.大数加法</h3> <ul><li>牛客网，<a href="https://www.nowcoder.com/questionTerminal/c56f6c70fb3f4849bc56e33ff2a50b6b" target="_blank" rel="noopener noreferrer">两个链表生成相加链表<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <div class="language-txt line-numbers-mode"><pre class="language-text"><code>1、『逆向思维』去模拟
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><h3 id="_1-2-大数乘法⭐️"><a href="#_1-2-大数乘法⭐️" class="header-anchor">#</a> 1.2.大数乘法⭐️</h3> <ul><li>牛客网，<a href="https://blog.nowcoder.net/n/21c559cb23e74786888345b361fa0c62" target="_blank" rel="noopener noreferrer">大数乘法<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>（两个正数版本）『我的博客题解』</li> <li>乘法的坑比加法多！✔️✔️✔️</li> <li><a href="https://leetcode-cn.com/problems/multiply-strings/" target="_blank" rel="noopener noreferrer">LeetCode43. 字符串相乘<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a> <ul><li>对『写代码前，测试先行』的理解更深刻</li></ul></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token number">1</span>、注意，两个为<span class="token number">0</span>的时候，要特判『不然，会有一个样例过不了』
<span class="token number">2</span>、『逆向思维』去模拟
<span class="token number">3</span>、用数组的下标<span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">2</span>去模拟，<span class="token number">10</span><span class="token operator">^</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">10</span><span class="token operator">^</span><span class="token number">1</span>啥的
<span class="token number">4</span>、一定要找到第<span class="token number">1</span>个不是<span class="token number">0</span>的数字，然后再组装回来
    
样例举例
Len1 Len2   Len		长度
<span class="token number">0</span>	 <span class="token number">123</span>    <span class="token number">0</span>		特判
<span class="token number">123</span>  <span class="token number">0</span>	    <span class="token number">0</span>		特判	
<span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">--</span><span class="token operator">-</span>    
<span class="token number">2</span>    <span class="token number">3</span>      <span class="token number">6</span>		Len1<span class="token operator">+</span>Len2<span class="token operator">-</span><span class="token number">1</span>
<span class="token number">2</span>    <span class="token number">5</span>      <span class="token number">10</span>		Len1<span class="token operator">+</span>Len2
<span class="token number">10</span>   <span class="token number">10</span>     <span class="token number">100</span>     Len1<span class="token operator">+</span>Len2<span class="token operator">-</span><span class="token number">1</span>
<span class="token number">20</span>   <span class="token number">50</span>     <span class="token number">1000</span>	Len1<span class="token operator">+</span>Len2
规律：我们的结果最大只需开
    Len1<span class="token operator">+</span>Len2
    然后，自己想办法，获得啥时候<span class="token operator">-</span><span class="token number">1</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br></div></div><div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    string <span class="token function">multiply</span><span class="token punctuation">(</span>string num1<span class="token punctuation">,</span> string num2<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        
        <span class="token comment">//代码健壮性</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token operator">==</span>num1<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">||</span> <span class="token number">0</span><span class="token operator">==</span>num2<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">throw</span> <span class="token string">&quot;error num1.size()||nums2.size()&quot;</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        
        string res<span class="token punctuation">;</span>
        <span class="token comment">//*0的特判</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">1</span><span class="token operator">==</span>num1<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> <span class="token string">'0'</span><span class="token operator">==</span>num1<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> res<span class="token operator">+=</span><span class="token string">&quot;0&quot;</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">1</span><span class="token operator">==</span>num2<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> <span class="token string">'0'</span><span class="token operator">==</span>num2<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> res<span class="token operator">+=</span><span class="token string">&quot;0&quot;</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token function">reverse</span><span class="token punctuation">(</span> num1<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> num1<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">reverse</span><span class="token punctuation">(</span> num2<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> num2<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">//可能是Len1+Len2-1  Len1+Len2 两种</span>
        <span class="token comment">//vector自动初始化为全0</span>
        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">temp</span><span class="token punctuation">(</span> num1<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">+</span>num2<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        
        <span class="token keyword">for</span><span class="token punctuation">(</span> <span class="token keyword">int</span> one<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> one<span class="token operator">&lt;</span>num1<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>one <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> two<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> two<span class="token operator">&lt;</span>num2<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>two <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token keyword">int</span> val<span class="token operator">=</span><span class="token punctuation">(</span>num1<span class="token punctuation">[</span>one<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">'0'</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>num2<span class="token punctuation">[</span>two<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">'0'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                temp<span class="token punctuation">[</span> one<span class="token operator">+</span>two <span class="token punctuation">]</span><span class="token operator">+=</span>val<span class="token punctuation">;</span>
                
                <span class="token comment">//注意要处理进位！！</span>
                <span class="token keyword">int</span> carry<span class="token operator">=</span>temp<span class="token punctuation">[</span>one<span class="token operator">+</span>two<span class="token punctuation">]</span><span class="token operator">/</span><span class="token number">10</span><span class="token punctuation">;</span>
                temp<span class="token punctuation">[</span>one<span class="token operator">+</span>two<span class="token punctuation">]</span><span class="token operator">%=</span><span class="token number">10</span><span class="token punctuation">;</span>

                <span class="token keyword">int</span> curPos<span class="token operator">=</span>one<span class="token operator">+</span>two<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
                <span class="token keyword">while</span><span class="token punctuation">(</span> carry <span class="token punctuation">)</span>
                <span class="token punctuation">{</span>
                    temp<span class="token punctuation">[</span> curPos <span class="token punctuation">]</span><span class="token operator">+=</span>carry<span class="token punctuation">;</span>
                    carry<span class="token operator">=</span>temp<span class="token punctuation">[</span> curPos <span class="token punctuation">]</span><span class="token operator">/</span><span class="token number">10</span><span class="token punctuation">;</span>
                    temp<span class="token punctuation">[</span>curPos<span class="token punctuation">]</span><span class="token operator">%=</span><span class="token number">10</span><span class="token punctuation">;</span>
                    <span class="token operator">++</span>curPos<span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">int</span> pos<span class="token operator">=</span>num1<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">+</span>num2<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> pos<span class="token operator">--</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> temp<span class="token punctuation">[</span>pos<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token keyword">break</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
        
        <span class="token comment">//搞定，10*10=100，temp中显示的0010这样的状况</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> pos<span class="token operator">&gt;=</span><span class="token number">0</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            res<span class="token operator">+=</span><span class="token punctuation">(</span>temp<span class="token punctuation">[</span>pos<span class="token punctuation">]</span><span class="token operator">+</span><span class="token string">'0'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token operator">--</span>pos<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> res<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br></div></div><h3 id="_1-3-大数阶乘"><a href="#_1-3-大数阶乘" class="header-anchor">#</a> 1.3.大数阶乘</h3> <ul><li>N的<a href="https://www.nowcoder.com/practice/f54d8e6de61e4efb8cce3eebfd0e0daa?tab=answerKey" target="_blank" rel="noopener noreferrer">阶乘<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <blockquote><p>参考题解：<a href="https://blog.nowcoder.net/n/158ab1f38b3a4e75b79788e92139a8e2" target="_blank" rel="noopener noreferrer">牛客网<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></blockquote> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>用<span class="token keyword">long</span>数组存储阶乘结果，数组中的每个数存储阶乘的<span class="token number">4</span>位<span class="token number">10</span>进制数，不足的用<span class="token number">0</span>补充。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br></div></div><h2 id="_02-stl提取出“全排列”『模板』"><a href="#_02-stl提取出“全排列”『模板』" class="header-anchor">#</a> 02.STL提取出“全排列”『模板』</h2> <ul><li><a href="https://leetcode-cn.com/problems/permutations/" target="_blank" rel="noopener noreferrer">46. 全排列<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>不含重复数字的数组</li> <li><a href="https://leetcode-cn.com/problems/permutations-ii/" target="_blank" rel="noopener noreferrer">47. 全排列 II<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>可包含重复数字的序列</li></ul> <h3 id="_2-1-不含重复数字-可包含重复数字『均可』"><a href="#_2-1-不含重复数字-可包含重复数字『均可』" class="header-anchor">#</a> 2.1.不含重复数字/可包含重复数字『均可』</h3> <ul><li><p><code>next_permutation</code>的源代码实现</p></li> <li><p><font style="background:yellow;"><code>iter_swap()</code>函数可以直接用</font></p></li> <li><p>下一个排列的算法模板：『Left（前边）  Right（后边） 』</p> <ul><li><code>next_permutation()</code>会取得<code>[Left,Right)</code>所标示之序列的下一个排列组合。</li> <li>如果没有下一个排列组合，便返回<code>false</code>，否则返回<code>true</code></li> <li>『4步伐』
<ul><li>1.首先，从『最尾端开始往前』寻找两个相邻元素，令<strong>靠近左边的第1元素</strong>为LeftOne，<strong>靠近左边的第二元素</strong>为LeftTwo，且满足<font style="background:yellow;"><code>LeftOne&lt; LeftTwo</code></font></li> <li>2.<strong>找到这样一组相邻元素后</strong>，再从『最尾端开始往前』检验,找出<strong>第1个</strong>大于LeftOne（<font style="background:yellow;"><code>LeftOne&lt;Temp</code></font>）的元素，令为Temp</li> <li>3.<code>iter_swap( LeftOne, Temp )</code></li> <li>4.再将<strong>LeftTwo及其之后</strong>的所有元素<strong>颠倒</strong>排列</li></ul></li></ul></li> <li><p>上1个排列的算法『<font style="background:yellow;">区别：见标记黄色背景的位置</font></p> <ul><li><code>prev_permutation()</code>会取得<code>[Left,Right)</code>所标示之序列的上一个排列组合。</li> <li>如果没有上一个排列组合，便返回<code>false</code>，否则返回<code>true</code></li> <li>『4步伐』
<ul><li>1.首先，从『最尾端开始往前』寻找两个相邻元素，令<strong>靠近左边的第1元素</strong>为LeftOne，<strong>靠近左边的第二元素</strong>为LeftTwo，且满足<font style="background:yellow;"><code>LeftOne&gt; LeftTwo</code></font></li> <li>2.<strong>找到这样一组相邻元素后</strong>，再从『最尾端开始往前』检验,找出<strong>第1个</strong>小于LeftOne（<font style="background:yellow;"><code>LeftOne&gt;Temp</code></font>）的元素，令为Temp</li> <li>3.<code>iter_swap( LeftOne, Temp )</code></li> <li>4.再将<strong>LeftTwo及其之后</strong>的所有元素<strong>颠倒</strong>排列</li></ul></li></ul></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">//下一个排列的算法模板</span>
<span class="token keyword">bool</span> <span class="token function">next_permutationMySelf</span>
    <span class="token punctuation">(</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator Left<span class="token punctuation">,</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator Right <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span> Left<span class="token operator">==</span>Right <span class="token operator">||</span> <span class="token number">1</span><span class="token operator">==</span><span class="token punctuation">(</span>Right<span class="token operator">-</span>Left<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token comment">//空区间或者只有1个元素的区间，所以没有下一个排列</span>
    <span class="token punctuation">{</span>
        cout<span class="token operator">&lt;&lt;</span><span class="token string">&quot;111&quot;</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
        <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token comment">//LeftOne指向倒数第2的位置</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator LeftOne<span class="token operator">=</span>Right<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">;</span>
    <span class="token comment">//LeftTwo指向倒数第1的位置</span>
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator LeftTwo<span class="token operator">=</span>Right<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
    
    <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token number">1</span> <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token operator">*</span>LeftOne <span class="token operator">&lt;</span> <span class="token operator">*</span>LeftTwo <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//2.找到这样一组相邻元素后，再从最尾端开始往前检验,找出第1个大于LeftOne的元素，令为Temp</span>
            vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">::</span>iterator Temp<span class="token operator">=</span>Right<span class="token punctuation">;</span>
            <span class="token operator">--</span>Temp<span class="token punctuation">;</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token operator">!</span><span class="token punctuation">(</span> <span class="token operator">*</span>LeftOne <span class="token operator">&lt;</span> <span class="token operator">*</span>Temp <span class="token punctuation">)</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token operator">--</span>Temp<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            
            <span class="token function">iter_swap</span><span class="token punctuation">(</span> LeftOne<span class="token punctuation">,</span> Temp <span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//3.iter_swap( LeftOne, Temp )这个函数可以直接调用</span>
            <span class="token function">reverse</span><span class="token punctuation">(</span> LeftTwo<span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>	<span class="token comment">//4.再将LeftTwo之后的所有元素颠倒排列.</span>
            <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        
        <span class="token comment">//如果LeftOne到尽头，表示已经是cba这样的形式了，没有下一个排列了</span>
        <span class="token comment">//在return false前，做个好事，顺路把它给倒转了</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> LeftOne<span class="token operator">==</span>Left <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token function">reverse</span><span class="token punctuation">(</span> Left<span class="token punctuation">,</span> Right <span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">//易错点：如果*LeftOne &lt; *LeftTwo不满足，那么都要减少</span>
        <span class="token operator">--</span>LeftOne<span class="token punctuation">;</span>
        <span class="token operator">--</span>LeftTwo<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    <span class="token comment">//如果是LeetCode可能需要吃这个</span>
    <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>


<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    vector<span class="token operator">&lt;</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;&gt;</span> <span class="token function">permuteUnique</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        vector<span class="token operator">&lt;</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token operator">&gt;</span> ret<span class="token punctuation">;</span>
        <span class="token function">sort</span><span class="token punctuation">(</span> nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> nums<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">do</span>
        <span class="token punctuation">{</span>
            ret<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token keyword">while</span><span class="token punctuation">(</span> <span class="token function">next_permutationMySelf</span><span class="token punctuation">(</span>nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> nums<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> ret<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br></div></div><h2 id="_03-马拉车算法『模板』"><a href="#_03-马拉车算法『模板』" class="header-anchor">#</a> 03.马拉车算法『模板』</h2> <ul><li>Manacher『马拉车算法』</li> <li>2020-07-16</li> <li>一种求最长回文串的线性算法</li></ul> <h3 id="_3-1-马拉车算法杂谈"><a href="#_3-1-马拉车算法杂谈" class="header-anchor">#</a> 3.1.马拉车算法杂谈</h3> <p>1）利用对称性来降低时间复杂度
2）可以看做是<strong>中心拓展法</strong>的一种优秀的剪枝
3）马拉车算法可以在<strong>线性时间</strong>内找出<strong>以任何位置为中心</strong>的最大回文串</p> <h3 id="_3-2-代码实现"><a href="#_3-2-代码实现" class="header-anchor">#</a> 3.2.代码实现</h3> <p><img src="https://cdn.jsdelivr.net/gh/HACV/picture/img/2020_07_16_Manacher_01.png" alt="2020_07_16_Manacher_01"></p> <p>参考链接：<a href="https://www.bilibili.com/video/BV1iW411W7iu?from=search&seid=2322527561023243984" target="_blank" rel="noopener noreferrer">电子科技大学38min左右<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstdio&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;algorithm&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;cstring&gt;</span> </span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> MAXN<span class="token operator">=</span><span class="token number">110010</span><span class="token punctuation">;</span>
<span class="token keyword">char</span> Ma<span class="token punctuation">[</span>MAXN<span class="token operator">*</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//预处理后的字符串 </span>
<span class="token keyword">int</span> Radius<span class="token punctuation">[</span>MAXN<span class="token operator">*</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//以其为中心的回文的半径Radius </span>

<span class="token keyword">void</span> <span class="token function">Manacher</span><span class="token punctuation">(</span><span class="token keyword">char</span> s<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span><span class="token keyword">int</span> len<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">int</span> l<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
	Ma<span class="token punctuation">[</span>l<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token string">'$'</span><span class="token punctuation">;</span>
	Ma<span class="token punctuation">[</span>l<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token string">'#'</span><span class="token punctuation">;</span>
	
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		Ma<span class="token punctuation">[</span>l<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
		Ma<span class="token punctuation">[</span>l<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token string">'#'</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	Ma<span class="token punctuation">[</span>l<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//其实是对字符数组的收尾，'\0' </span>
	
	
	<span class="token comment">//______________________________核心代码begin </span>
	<span class="token comment">//center表示回文串的中心点 </span>
	<span class="token keyword">int</span> right<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>center<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
	
	<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>l<span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span> 
	<span class="token punctuation">{</span> 
		<span class="token comment">//利用对称性，进行剪枝 </span>
		Radius<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>right<span class="token operator">&gt;</span>i<span class="token operator">?</span><span class="token function">min</span><span class="token punctuation">(</span>Radius<span class="token punctuation">[</span><span class="token number">2</span><span class="token operator">*</span>center<span class="token operator">-</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>right<span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token operator">:</span><span class="token number">1</span><span class="token punctuation">;</span>
		
		<span class="token comment">//从中心往两边扩展 </span>
		<span class="token keyword">while</span><span class="token punctuation">(</span>Ma<span class="token punctuation">[</span>i<span class="token operator">+</span>Radius<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">==</span>Ma<span class="token punctuation">[</span>i<span class="token operator">-</span>Radius<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			Radius<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
		
		<span class="token comment">//获取当前最长回文串的中心center和右侧最右边right </span>
		<span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">+</span>Radius<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">&gt;</span>right<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			right<span class="token operator">=</span>i<span class="token operator">+</span>Radius<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
			center<span class="token operator">=</span>i<span class="token punctuation">;</span>
		<span class="token punctuation">}</span>
	<span class="token punctuation">}</span>
	<span class="token comment">//______________________________核心代码end	</span>
	
	
<span class="token punctuation">}</span>


<span class="token keyword">char</span> str<span class="token punctuation">[</span>MAXN<span class="token punctuation">]</span><span class="token punctuation">;</span> 
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%s&quot;</span><span class="token punctuation">,</span>str<span class="token punctuation">)</span><span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		<span class="token keyword">int</span> len<span class="token operator">=</span><span class="token function">strlen</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token function">Manacher</span><span class="token punctuation">(</span>str<span class="token punctuation">,</span>len<span class="token punctuation">)</span><span class="token punctuation">;</span>
		
		<span class="token keyword">int</span> ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
		<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">2</span><span class="token operator">*</span>len<span class="token operator">+</span><span class="token number">2</span><span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
		<span class="token punctuation">{</span>
			ans<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span>Radius<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//回文长度和Radius[]的关系正好为-1（可以证明） </span>
		<span class="token punctuation">}</span>
		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
	
	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
 <span class="token punctuation">}</span> 
 
 

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br></div></div><p>另外的</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;vector&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;string&gt;</span></span>

<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

string <span class="token function">Mannacher</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token comment">//插入&quot;#&quot;</span>
    string t<span class="token operator">=</span><span class="token string">&quot;$#&quot;</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        t<span class="token operator">+=</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        t<span class="token operator">+=</span><span class="token string">&quot;#&quot;</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    
    vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">p</span><span class="token punctuation">(</span>t<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">//mx表示某个回文串延伸在最右端半径的下标，id表示这个回文子串最中间位置下标</span>
    <span class="token comment">//resLen表示对应在s中的最大子回文串的半径，resCenter表示最大子回文串的中间位置</span>
    <span class="token keyword">int</span> mx<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>id<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>resLen<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>resCenter<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>

     <span class="token comment">//建立p数组</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>t<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token operator">++</span>i<span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>mx<span class="token operator">&gt;</span>i<span class="token operator">?</span><span class="token function">min</span><span class="token punctuation">(</span>p<span class="token punctuation">[</span><span class="token number">2</span><span class="token operator">*</span>id<span class="token operator">-</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>mx<span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token operator">:</span><span class="token number">1</span><span class="token punctuation">;</span>

        <span class="token comment">//遇到三种特殊的情况，需要利用中心扩展法</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>t<span class="token punctuation">[</span>i<span class="token operator">+</span>p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">==</span>t<span class="token punctuation">[</span>i<span class="token operator">-</span>p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">++</span>p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>

        <span class="token comment">//半径下标i+p[i]超过边界mx，需要更新</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>mx<span class="token operator">&lt;</span>i<span class="token operator">+</span>p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            mx<span class="token operator">=</span>i<span class="token operator">+</span>p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            id<span class="token operator">=</span>i<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">//更新最大回文子串的信息，半径及中间位置</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>resLen<span class="token operator">&lt;</span>p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            resLen<span class="token operator">=</span>p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            resCenter<span class="token operator">=</span>i<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//最长回文子串长度为半径-1，起始位置为中间位置减去半径再除以2</span>
    <span class="token keyword">return</span> s<span class="token punctuation">.</span><span class="token function">substr</span><span class="token punctuation">(</span><span class="token punctuation">(</span>resCenter<span class="token operator">-</span>resLen<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">,</span>resLen<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token function">Mannacher</span><span class="token punctuation">(</span><span class="token string">&quot;12212&quot;</span><span class="token punctuation">)</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token function">Mannacher</span><span class="token punctuation">(</span><span class="token string">&quot;122122&quot;</span><span class="token punctuation">)</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token function">Mannacher</span><span class="token punctuation">(</span><span class="token string">&quot;noon&quot;</span><span class="token punctuation">)</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    <span class="token function">system</span><span class="token punctuation">(</span><span class="token string">&quot;pause&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br></div></div><h2 id="_04-求众数『模板』"><a href="#_04-求众数『模板』" class="header-anchor">#</a> 04.求众数『模板』</h2> <ul><li>易错：摩尔投票法『仅能』解决非数学上的众数！</li></ul> <h3 id="_4-1-『众数的广泛例子』"><a href="#_4-1-『众数的广泛例子』" class="header-anchor">#</a> 4.1.『众数的广泛例子』</h3> <p>比如，1,1,1,2,2,3,3,应该返回1而不是3『如果是摩尔投票法，会返回3』</p> <p>『注意：摩尔投票法无法解决“数学上”的众数！！！！』</p> <ul><li>解法：哈希+遍历。。。</li></ul> <h3 id="_4-2-面试题-17-10-主要元素『众数的特例』"><a href="#_4-2-面试题-17-10-主要元素『众数的特例』" class="header-anchor">#</a> 4.2.<a href="https://leetcode-cn.com/problems/find-majority-element-lcci/" target="_blank" rel="noopener noreferrer">面试题 17.10. 主要元素<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>『众数的特例』</h3> <blockquote><p>注意：使用摩尔投票法</p></blockquote> <ul><li><p>相同意思的题目：<a href="https://leetcode-cn.com/problems/majority-element/" target="_blank" rel="noopener noreferrer">169. 多数元素<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li> <li><p><code>pairing</code> 阶段必然返回数组中的一个众数，但是由于众数不止一个，所以还需要经过 <code>counting</code> 阶段确认是否存在主要元素。</p></li></ul> <blockquote><p>数组中占比『『超过一半』』的元素称之为主要元素。给定一个<strong>整数</strong>数组，找到它的主要元素。若没有，返回-1。</p></blockquote> <ul><li>注意：这个是特例：因为1，1，1,2,2,3,3,3就只能返回-1了『和数学中的概念不一样』</li> <li>此外，由于1/2，显然，我们排序后获取中间的数字也是OK的。。</li></ul> <h3 id="摩尔投票法讲解："><a href="#摩尔投票法讲解：" class="header-anchor">#</a> 摩尔投票法讲解：</h3> <ul><li>核心：一组是众数！一组是奇奇怪怪的各大阵营的敌军！</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">int</span> <span class="token function">majorityElement</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token keyword">int</span> CurNumMode<span class="token operator">=</span><span class="token number">0x3f3f3f</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> count<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//表示我方已经开始『领旗』，但是根基不稳</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span> <span class="token keyword">auto</span> n <span class="token operator">:</span> nums <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> CurNumMode<span class="token operator">==</span>n <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token operator">++</span>count<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//根基不稳的可以被取代</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token operator">==</span>count <span class="token punctuation">)</span>
                <span class="token punctuation">{</span>
                    CurNumMode<span class="token operator">=</span>n<span class="token punctuation">;</span>
                    <span class="token comment">//下面的代码『故意写，用来强化意思』</span>
                    count<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//表示我方已经开始『领旗』，但是根基不稳</span>
                <span class="token punctuation">}</span>
                <span class="token keyword">else</span>
                <span class="token punctuation">{</span>
                    <span class="token operator">--</span>count<span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">int</span> Len<span class="token operator">=</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> sum<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span> <span class="token keyword">auto</span> n <span class="token operator">:</span> nums <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> CurNumMode<span class="token operator">==</span>n <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token operator">++</span>sum<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span> sum<span class="token operator">&gt;</span><span class="token punctuation">(</span>Len<span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> CurNumMode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">else</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br></div></div><h3 id="_4-3-『众数的特例-特例』229-求众数-ii"><a href="#_4-3-『众数的特例-特例』229-求众数-ii" class="header-anchor">#</a> 4.3.『众数的特例+特例』<a href="https://leetcode-cn.com/problems/majority-element-ii/" target="_blank" rel="noopener noreferrer">229. 求众数 II<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></h3> <ul><li>给定一个大小为 <em>n</em> 的整数数组，找出其中所有出现超过 <code>⌊ n/3 ⌋</code> 次的元素。</li></ul> <blockquote><p>『可以对』<strong>摩尔投票算法进行改进：</strong></p></blockquote> <h2 id="_05-位运算"><a href="#_05-位运算" class="header-anchor">#</a> 05.位运算</h2> <h3 id="_5-1-交换"><a href="#_5-1-交换" class="header-anchor">#</a> 5.1.交换</h3> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">int</span> a<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> b<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">;</span>
a<span class="token operator">=</span>a<span class="token operator">^</span>b<span class="token punctuation">;</span>
b<span class="token operator">=</span>a<span class="token operator">^</span>b<span class="token punctuation">;</span>
a<span class="token operator">=</span>a<span class="token operator">^</span>b<span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><blockquote><p>记忆：观察知道，右边都是a^b</p></blockquote> <h3 id="_5-2-异或的性质"><a href="#_5-2-异或的性质" class="header-anchor">#</a> 5.2.异或的性质</h3> <ul><li><p><code>0^x=0</code></p></li> <li><div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code>如果：
    a<span class="token operator">^</span>b<span class="token operator">=</span>other<span class="token punctuation">;</span>
那么：
    <span class="token punctuation">(</span>a<span class="token operator">^</span>other<span class="token operator">==</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token punctuation">(</span>b<span class="token operator">^</span>other<span class="token operator">==</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div></li></ul></div> <div class="page-edit"><!----> <!----></div> <!----> </div> <!----></div></div>
    <script src="/assets/js/app.c70e21ad.js" defer></script><script src="/assets/js/67.26f84d32.js" defer></script>
  </body>
</html>
